#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007
struct node
{
    int x;
    int y;
    int weight;
    bool operator<(const node& b) const
    {
        return weight > b.weight;
    }

    node(int _x, int _y, int _weight):x(_x),y(_y),weight(_weight){}
};
class Solution {
public:
    int swimInWater(std::vector<std::vector<int>>& grid) {
        std::array<int,5> move= {-1,0,1,0,-1};
        int n = grid.size();
        int m = grid[0].size();
        std::vector<std::vector<int>> dis(n,std::vector<int>(m,std::numeric_limits<int>::max()));
        std::vector<std::vector<bool>> visited(n,std::vector<bool>(m,false));
        std::priority_queue<node> pq;
        // 修正 1：初始节点 weight 设为 0（起点无消耗）
        pq.emplace(0,0,grid[0][0]);  // 原代码：grid[0][0]
        dis[0][0] = 0;  // 补充：初始化起点的 dis 值
        // 注意：此处不应标记 visited[0][0] = true
        
        while(!pq.empty()) {
            node cur = pq.top();
            pq.pop();
            // 修正 2：仅在弹出节点时检查是否已访问，避免错过更优路径
            if(visited[cur.x][cur.y]) continue;
            visited[cur.x][cur.y] = true;  // 此时才标记为已访问
            
            if(cur.x == n-1 && cur.y == m-1) {
                return cur.weight;
            }
            
            for(int i=0;i<4;i++) {
                int x = cur.x + move[i];
                int y = cur.y + move[i+1];
                if(x<0||x>=n||y<0||y>=m) continue;  // 简化边界判断（原代码 x>n-1 等价于 x>=n）
                int c = std::max(cur.weight, grid[x][y]);
                if(dis[x][y] > c) {
                    dis[x][y] = c;
                    pq.emplace(x,y,c);  // 此时推送节点是正确的（配合上述修正）
                    // 移除：visited[x][y] = true; （不再提前标记）
                }
            }
        }
        return -1;
    }
};
